The present invention relates generally to forward error correction systems, and in particular to forward error correction systems using iteratively decoded codes.
Electronic communication channels provide for the transmission of large quantities of information. Communication channels, however, tend to be noisy. The noise inherent in a communication channel tends to produce errors in the transmitted information. Accordingly, redundant information is often included in transmitted data, with the redundant information allowing a receiver to reconstruct the transmitted message.
A large number of coding schemes exist for determining the amount and nature of the redundant information included in transmitted data. The coding schemes tend to vary somewhat in terms of the number of error bits determinable for a given number of information bits and number of redundant bits, the ability to locate the error bits, the ability to correct burst errors, and other various characteristics. In addition, for any particular coding scheme there tend to be a number of codes available, with the codes often varying in terms of the number of information bits and the number of redundant bits. Further, codes may be systematic, with redundant bits added to, for example, the end of a stream of information bits, or non-systematic, with the information bits and the redundant bits combined in various ways to form a transmitted bit stream.
Coding schemes and actual codes are often selected for use based on various criteria. These criteria include the expected bit error rate (BER) of the transmission system, the desired BER, the amount of transmission overhead associated with a particular code, and the amount of processing necessary to process the code.
Processing of the code generally entails forming code symbols out of information symbols prior to transmission, and determining the information symbols from received versions of the code symbols, i.e. received symbols, upon reception. Forming of code symbols is often termed encoding, and determining the information symbols from received symbols is often termed decoding. Different codes have different processing requirements for encoding and for decoding.
One type of codes are low density parity check codes. Low density parity check codes are discussed, for example, in R. G. Gallager, Low Density Parity Check Codes, IRE Trans. Info. Theory, IR-8:21-28 (January 1962), the disclosure of which is incorporated by reference. Generally, low density parity check codes are parity check codes with a parity check matrix containing mostly zeroes. Somewhat specifically, the parity check matrix may be defined in terms of block length N, the number of ones per column j, and the number of ones per row k (N,j,k). The ones in the parity check matrix are preferably randomly distributed within the matrix.
A parity check matrix may be formed by first generating a submatrix having only a single one per column, and then randomly permutating the columns of the submatrix to form additional submatrices until the entire parity check matrix is formed. Thus, for any (j,k) code a number of parity check matrices of varying, or possibly the same, block lengths may be formed.
An example parity check matrix is provided as FIG. 1. The parity check matrix, sometimes referred to as H, is for a (3,4) regular low density parity check (LDPC) code. The parity check matrix has a block length n of 12. As illustrated the parity check matrix has three ones per column and four ones per row. The parity check matrix is used for code words 12 of symbols based on information words of 3 symbols.
Parity check matrices for LDPC codes are often discussed with respect to their associated bipartite graph. A bipartite graph, at least in this context, includes a number of variable nodes and a number of check nodes. The variable nodes are arranged in a first line and the check nodes are arranged in a second line. The number of variable nodes is the same as the number of symbols in the code word. The number of check nodes is equal to the number of constraints, or checks, placed on the variable nodes. Lines, sometimes referred to as edges, connect the variable nodes and the check nodes, and indicate which checks apply to which variables.
A bipartite graph for the parity check matrix of FIG. 1 is shown in FIG. 2. The graph includes 12 variable nodes and 9 check nodes. Each of the variable nodes 21 is connected by lines 25 to three check nodes, indicating that each variable has three parity checks. Each of the check nodes 23 is connected by lines to four variable nodes, indicating that each check is part of parity checks for four variables.
Decoding may be accomplished using a variety of methods, including using the parity check directly to determine error symbols. More generally, however, error correction capability may be increased using iterative decoding methods such as the sum-product algorithm, or through use of what is sometimes more generally referred to as belief propagation. The sum product algorithm is described more fully, for example, in N. Wiberg, Codes and Decoding on General Graphs, Linkoping Studies in Science and Technology, Dissertations No. 440 (Linkoping University, 1996), the disclosure of which is incorporated by reference. In short, in these methods probabilities of symbol values are determined and assigned to variables, and then redetermined and assigned multiple times.